#include "Tree.cpp"


// 非递归遍历
stack<TreeNode*> s;


void preorderTree(TreeNode* root){
    s.push(root);
    while(!s.empty()) {
        // 访问当前树
        TreeNode *p = s.top();
        s.pop();
        visit(p->data);
        if (p->rightChild != NULL) {
           s.push(p->rightChild);
        }
        if (p->leftChild != NULL) {
            s.push(p->leftChild);
        }
    }
}

void inOrderTree(TreeNode* root){
    TreeNode *p = root;
    while(p!= NULL || !s.empty()) {
        // 访问当前树
        if (p != NULL) {
            s.push(p);
            // 访问左子树
            p = p->leftChild;
        }else {
            p = s.top();
            s.pop();
            visit(p->data);
            p = p->rightChild;
        }
    }
}



void lastOrderTree(TreeNode* root){
    TreeNode *p = root;
    TreeNode * pre = NULL;
    while(p!= NULL || !s.empty()) {
        // 访问当前树
        if (p != NULL) {
            s.push(p);
            // 访问左子树
            p = p->leftChild;
        }else {
            p = s.top();
            if (p->rightChild == NULL || p->rightChild == pre) {
                // 访问当前节点
                visit(p->data);
                pre = p;
                s.pop();
                p = NULL;
            }else {
                // 访问右子树
                p = p->rightChild;
            }
        }
    }
}

int main() {
    Tree tree = CreateTreeByFile("Day-3-1.txt");
    preorderTree(tree);
}